package com.hc.programming.math;

/**
 * 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
 * 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
 * 请你计算并返回达到楼梯顶部的最低花费。
 * <p>
 * 示例 1：
 * 输入：cost = [10,15,20]
 * 输出：15
 * 解释：你将从下标为 1 的台阶开始。
 * - 支付 15 ，向上爬两个台阶，到达楼梯顶部。
 * 总花费为 15 。
 * 示例 2：
 * 输入：cost = [1,100,1,1,1,100,1,1,100,1]
 * 输出：6
 * 解释：你将从下标为 0 的台阶开始。
 * - 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
 * - 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
 * - 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
 * - 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
 * - 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
 * - 支付 1 ，向上爬一个台阶，到达楼梯顶部。
 * 总花费为 6 。
 * <p>
 * 提示：
 * 2 <= cost.length <= 1000
 * 0 <= cost[i] <= 999
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/9/2 20:31
 */
public class 使用最小花费爬楼梯 {
    public static void main(String[] args) {
        System.out.println("[10,15,20]=15,--" + minCostClimbingStairs(new int[]{10, 15, 20}));
        System.out.println("[1,0,0,0]=0,--" + minCostClimbingStairs(new int[]{1, 0, 0, 0}));
        System.out.println("[1,1,1,0]=1,--" + minCostClimbingStairs(new int[]{1, 1, 1, 0}));
        System.out.println("[1,100,1,1,1,100,1,1,100,1]=6,--" + minCostClimbingStairs(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));
        System.out.println("[2,2,1,0]=2,--" + minCostClimbingStairs(new int[]{2, 2, 1, 0}));
    }

    public static int minCostClimbingStairs(int[] cost) {
        return 动态规划(cost);
    }

    /**
     * dp[i]: 到第i步最小费用
     * 递推公式： dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i]
     * dp[0] = cost[0]; dp[1] = cost[1]
     * 正逆向均可
     */
    public static int 动态规划(int[] cost) {
        if (cost.length < 2) return 0;
        int[] dp = new int[cost.length+1];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.length; i++) {
            dp[i] = Math.min(dp[i-1], dp[i-2]) + cost[i];
        }
        dp[cost.length] = Math.min(dp[cost.length - 1], dp[cost.length - 2]);
        return dp[cost.length];
    }
}
